정보과학회논문지 (Journal of KIISE)
Current Result Document :
| 한글제목(Korean Title) |
데이터 재사용을 고려한 효율적인 연속 서브 그래프 매칭 기법 |
| 영문제목(English Title) |
An Efficient Continuous Subgraph Matching Scheme Considering Data Reuse |
| 저자(Author) |
최도진
복경수
유재수
Dojin Choi
Kyoungsoo Bok
Jaesoo Yoo
|
| 원문수록처(Citation) |
VOL 46 NO. 08 PP. 0842 ~ 0851 (2019. 08) |
한글내용
(Korean Abstract) |
다양한 응용에서 그래프 스트림에 대한 활용이 증가됨에 따라 실시간으로 변화되는 서브 그래프를 탐색하기 위해서는 연속 서브 그래프 매칭 기법이 필요하다. 본 논문에서는 그래프 스트림에서의 색인 재사용과 분산 처리가 가능한 효율적인 연속 서브 그래프 매칭 기법을 제안한다. 서브 그래프 매칭 질의를 분산 처리하기 위해 차수 기반의 질의 분할 기법을 제안하고 그래프 스트림을 분할된 질의 기반으로 색인한다. 다수의 질의가 입력되는 환경에서 야기되는 색인의 부하를 감소시키기 위해서 색인 정보를 재사용한다. 또한, 각 서버의 색인 부하를 계산하는 비용 모델을 통해 질의 할당을 수행한다. 제안하는 기법은 스트림 환경에서 효율적인 분산 처리를 수행하기 위해 스톰에서 구현된다. 우수성을 입증하기 위해 다양한 성능 평가를 수행한다.
|
영문내용
(English Abstract) |
With an increase in the utilization of graph streams in various applications, a continuous subgraph matching scheme is required to search the subgraphs that undergo changes in real time. In this paper, we propose an efficient continuous subgraph matching scheme that reuses indexing and performs distributed processing in graph stream environments. In order to perform distributed processing, we propose a query decomposition method based on the degree and subsequently manage the decomposed subqueries as an index. The proposed scheme reuses indexing information to reduce the load on the index caused by the environment in which multiple queries are entered. We also conduct query allocation through a cost model that calculates the indexing load of each server. For efficient performance of distributed processing in stream environments, the proposed scheme was implemented in Storm. Various performance evaluations were conducted to demonstrate the superiority of the proposed scheme.
|
| 키워드(Keyword) |
서브 그래프 매칭
연속 질의 처리
분산 처리
스트림 처리
스톰
subgraph matching
continuous query processing
distributed processing
stream processing
storm
|
| 파일첨부 |
PDF 다운로드
|
